package com.wxg.algorithm.chapter04;

import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

public class HeapSortV1<T extends Comparable> implements ISort<T> {
    @Override
    public void sort(T[] arr) {
        int len = arr.length;
        MaxHeap<T> maxHeap = new MaxHeap<>(len);
        for (int i=0; i<len; i++){
            maxHeap.insert(arr[i]);
        }

        for (int i = len-1; i>=0; i--){
            arr[i] = maxHeap.extractMax();
        }
    }

    public static void main(String[] args) {
        HeapSortV1<Integer> hs = new HeapSortV1<>();

        int n = 1000000;
        Integer[] intArr01 = SortTestHelper.generateRandomArray(n, 0, n);

        SortTestHelper.testSort(hs, intArr01);

        Integer[] intArr02 = SortTestHelper.generateNearlyOrderedArray(n, 100);

        SortTestHelper.testSort(hs, intArr02);


    }
}
